Search for: All records

Abstract Given a countable structure, the Scott complexity measures the difficulty of characterizing the structure up to isomorphism. In this paper, we consider the Scott complexity of linear orders. For any limit ordinal , we construct a linear order whose Scott complexity is . This completes the classification of the possible Scott sentence complexities of linear orderings. Previously, there was only one known construction of any structure (of any signature) with Scott complexity , and our construction gives new examples, for example, rigid structures, of this complexity. Moreover, we can construct the linear orders so that not only does have Scott complexity , but there are continuum‐many structures and all such structures also have Scott complexity . In contrast, we demonstrate that there is no structure (of any signature) with Scott complexity that is only ‐equivalent to structures with Scott complexity . Our construction is based on functions that are almost periodic but not periodic, such as those arising from shifts of the ‐adic valuations. 

In this paper, we answer two questions on the complexities of decision problems of groups, each related to a classical result. First, Miller characterized the complexity of the isomorphism problem for finitely presented groups in 1971. We do the same for the isomorphism problem for recursively presented groups. Second, the fact that every Turing degree appears as the degree of the word problem of a finitely presented group is shown independently by multiple people in the 1960s. We answer the analogous question for degrees of ceers instead of Turing degrees. We show that the set of ceers which are computably equivalent to the word problem of a finitely presented group is [Formula: see text]-complete, which is the maximal possible complexity. 

Abstract A group is said to have rational growth with respect to a generating set if the growth series is a rational function. It was shown by Parry that certain torus bundle groups of even trace exhibits rational growth. We generalize this result to a class of torus bundle groups with odd trace.